class Solution {
public:
    bool IsBalanced_Solution(TreeNode* pRoot) {
        return dfs2(pRoot) != -1;
    }
 
    int dfs(TreeNode* pRoot) // 返回-1代表不是平衡二叉树，不返回-1的话返回的是树高
    {
        if(pRoot == nullptr)
            return 0;
        if(pRoot->left == nullptr && pRoot->right == nullptr)
            return 1;
        if(abs(dfs(pRoot->left) - dfs(pRoot->right)) > 1)
            return -1;
        if(dfs(pRoot->left) != -1 && dfs(pRoot->right) != -1)
            return max(dfs(pRoot->left), dfs(pRoot->right)) + 1;
        return -1;
    }
 
    int dfs2(TreeNode* pRoot) // 题解代码。返回-1代表不是平衡二叉树，不返回-1的话返回的是树高
    {
        if(pRoot == nullptr)
            return 0;
 
        int left = dfs(pRoot->left);
        if(left == -1) // 剪枝
            return -1;
 
        int right = dfs(pRoot->right);
        if(right == -1)
            return -1;
 
        return abs(left - right) <= 1 ? max(left, right) + 1 : -1;
    }
};